λ¬Έμ
Programmers - μΉ΄λ μ§ λ§μΆκΈ°
π Logic
private static int permutate(Card src) {
int ret = Integer.MAX_VALUE;
// 1λΆν° 6κΉμ§μ μΉ΄λκ° μ‘΄μ¬ν μ μλ€.
for (int n = 1; n <= 6; n++) {
// nμ ν΄λΉνλ μΉ΄λλ₯Ό μ μ₯νλ 리μ€νΈ
ArrayList<Card> cards = findNCard(n);
// μ νν μΉ΄λλ€μ΄ μλ κ²½μ°, ν¨μ€
if (cards.isEmpty()) continue;
// νμ¬ μμΉλΆν° μ νν μΉ΄λκΉμ§ κ°κΈ° μν 거리λ₯Ό κ³μ°
int one = bfs(src, cards.get(0)) + bfs(cards.get(0), cards.get(1)) + 2;
// oneμ μμμΌλ‘ μ§ν
int two = bfs(src, cards.get(1)) + bfs(cards.get(1), cards.get(0)) + 2;
// λ€μ§μ μΉ΄λλ₯Ό 보λμμ μ κ±°
removeCards(cards);
// μ¬κ· νΈμΆ μν
// oneμΌλ‘ μνν μΉ΄λ λ€μ§κΈ° μ΄ν, 컀μκ° card.get(1)μ μμ λ λ¨μ μΉ΄λλ€μ λν λ€μ§κΈ° μν
ret = Math.min(ret, one + permutate(cards.get(1)));
// twoλ‘ μνν μΉ΄λ λ€μ§κΈ° μ΄ν, 컀μκ° card.get(0)μ μμ λ λ¨μ μΉ΄λλ€μ λν λ€μ§κΈ° μν
ret = Math.min(ret, two + permutate(cards.get(0)));
// 1λ² μΉ΄λμ λν λ€μ§κΈ° μν ν, 2λ² μΉ΄λμ λν λ€μ§κΈ° μ§ν μμλ 1λ² μΉ΄λ λ€μ§κΈ°μ λν 볡μμ΄ νμνλ€.
restoreCards(cards, n);
}
if (ret == Integer.MAX_VALUE) return 0;
return ret;
}
- μ¬κ·λ₯Ό μννλ©΄μ, λͺ¨λ μΉ΄λ λ€μ§κΈ° μμλ₯Ό μ§ννλ©΄μ μ΅μ λΉμ©μ κ³μ°νλ€.
- μΉ΄λμ μΉ΄λ κ° μ΄λ μ μ΅μ μ‘°μ νμλ₯Ό ꡬνκΈ° μν΄ BFSλ₯Ό μννλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Card {
// ν, μ΄, μ΄λνκΈ° μν΄ νμν μ‘°μ νμ
int r;
int c;
int count;
public Card(int r, int c, int count) {
this.r = r;
this.c = c;
this.count = count;
}
}
class Solution {
static int[][] board;
static int[][] range = {{ -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }};
public int solution(int[][] board, int r, int c) {
this.board = board;
return permutate(new Card(r, c, 0));
}
private static int permutate(Card src) {
int ret = Integer.MAX_VALUE;
// 1λΆν° 6κΉμ§μ μΉ΄λκ° μ‘΄μ¬ν μ μλ€.
for (int n = 1; n <= 6; n++) {
// nμ ν΄λΉνλ μΉ΄λλ₯Ό μ μ₯νλ 리μ€νΈ
ArrayList<Card> cards = findNCard(n);
// μ νν μΉ΄λλ€μ΄ μλ κ²½μ°, ν¨μ€
if (cards.isEmpty()) continue;
// νμ¬ μμΉλΆν° μ νν μΉ΄λκΉμ§ κ°κΈ° μν 거리λ₯Ό κ³μ°
int one = bfs(src, cards.get(0)) + bfs(cards.get(0), cards.get(1)) + 2;
// oneμ μμμΌλ‘ μ§ν
int two = bfs(src, cards.get(1)) + bfs(cards.get(1), cards.get(0)) + 2;
// λ€μ§μ μΉ΄λλ₯Ό 보λμμ μ κ±°
removeCards(cards);
// μ¬κ· νΈμΆ μν
// oneμΌλ‘ μνν μΉ΄λ λ€μ§κΈ° μ΄ν, 컀μκ° card.get(1)μ μμ λ λ¨μ μΉ΄λλ€μ λν λ€μ§κΈ° μν
ret = Math.min(ret, one + permutate(cards.get(1)));
// twoλ‘ μνν μΉ΄λ λ€μ§κΈ° μ΄ν, 컀μκ° card.get(0)μ μμ λ λ¨μ μΉ΄λλ€μ λν λ€μ§κΈ° μν
ret = Math.min(ret, two + permutate(cards.get(0)));
// 1λ² μΉ΄λμ λν λ€μ§κΈ° μν ν, 2λ² μΉ΄λμ λν λ€μ§κΈ° μ§ν μμλ 1λ² μΉ΄λ λ€μ§κΈ°μ λν 볡μμ΄ νμνλ€.
restoreCards(cards, n);
}
if (ret == Integer.MAX_VALUE) return 0;
return ret;
}
private static int bfs(Card src, Card dest) {
boolean[][] visited = new boolean[4][4];
Queue<Card> queue = new LinkedList<>();
queue.add(src);
while(!queue.isEmpty()) {
Card now = queue.poll();
// λͺ©μ μ§μ λμ°©ν κ²½μ°, μ‘°μ νμλ₯Ό λ°ν
if (now.r == dest.r && now.c == dest.c) return now.count;
for (int i = 0; i < 4; i++) {
int nr = now.r + range[i][0], nc = now.c + range[i][1];
if (!isInBoundary(nr, nc)) continue;
// λ°©λ¬Ένμ§ μμ κ²½μ° μ‘°μ νμ κ°±μ
if (!visited[nr][nc]) {
visited[nr][nc] = true;
queue.add(new Card(nr, nc, now.count + 1));
}
// ctrlμ μ΄μ©ν΄ μ‘°μ κ°λ₯ν κ²½μ°
for (int j = 0; j < 2; j++) {
// λ€μ§μ΄μ§ μΉ΄λκ° μλ κ²½μ° μ’
λ£
if (board[nr][nc] != 0) break;
// ν λ² λ ν΄λΉ λ°©ν₯μΌλ‘ μ§ννμ λ κ²½κ³λ₯Ό λ²μ΄λλ κ²½μ°λ μ’
λ£
if (!isInBoundary(nr + range[i][0], nc + range[i][1])) break;
nr += range[i][0];
nc += range[i][1];
}
// nr, ncλ μ΄μ ν λ²μ μ΄λν μ μλ μμΉ
if (visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.add(new Card(nr, nc, now.count + 1));
}
}
return Integer.MAX_VALUE;
}
private static boolean isInBoundary(int r, int c) {
return r >= 0 && r < 4 && c >= 0 && c < 4;
}
private static ArrayList<Card> findNCard(int num) {
ArrayList<Card> cards = new ArrayList<>();
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (board[i][j] == num)
cards.add(new Card(i, j, 0));
return cards;
}
private static void removeCards(ArrayList<Card> cards) {
for (Card card : cards)
board[card.r][card.c] = 0;
}
private static void restoreCards(ArrayList<Card> cards, int num) {
for (Card card : cards)
board[card.r][card.c] = num;
}
}
βοΈ Review
-
μ²μμ ꡬννλ €ν μμ΄λμ΄λ,
mapμ μΉ΄λ λ²νΈλ³λ‘ μΉ΄λ μμΉλ₯Ό μ μ₯νκ³ , νμ¬ μ»€μμμ κ°μ₯ κ°κΉμ΄ μλ μΉ΄λλ₯Ό λ€μ§κ³ , ν΄λΉ μΉ΄λ μ§μ μ°Ύμ 컀μλ₯Ό μ΄λν ν λ€μ§κ³ λ₯Ό λ°λ³΅νλ λ°©μμ΄μλ€.- μκ°ν΄λ³΄λ μΉ΄λ μμκ° μ€μν μ μκ² λ€λΌλ κ±Έ κΉ¨λ¬μκ³ , ꡬνμ μ΄λ»κ² ν΄μΌ ν μ§ λͺ¨λ₯΄κ² μ΄μ ... νμ΄ μμμ μ°Έκ³ νλ€.